from fastapi import FastAPI, HTTPException
import uvicorn
from pydantic import BaseModel
from typing import List

app = FastAPI(title="二分查找服务API")


class BinarySearchInput(BaseModel):
    sorted_array: List[int]
    target: int


@app.post("/binary_search")
async def binary_search_endpoint(input: BinarySearchInput):
    """执行二分查找算法"""
    # 验证数组是否有序
    if not all(input.sorted_array[i] <= input.sorted_array[i + 1] for i in range(len(input.sorted_array) - 1)):
        raise HTTPException(
            status_code=400,
            detail="输入数组必须是升序排列"
        )

    left, right = 0, len(input.sorted_array) - 1
    iterations = 0

    while left <= right:
        iterations += 1
        mid = (left + right) // 2
        if input.sorted_array[mid] == input.target:
            return {
                "found": True,
                "index": mid,
                "iterations": iterations,
                "target": input.target
            }
        elif input.sorted_array[mid] < input.target:
            left = mid + 1
        else:
            right = mid - 1

    return {
        "found": False,
        "iterations": iterations,
        "target": input.target
    }


if __name__ == "__main__":
    uvicorn.run(app, host="0.0.0.0", port=8000)